Internet is formed of a plurality of networks connected to each other, wherein each of the constituent networks maintains its identity. Each network supports communication among devices connected to the networks, and the networks in their turn are connected by routers. Thus, Internet can be considered to comprise a mass of routers interconnected by links. Communication among nodes (routers) on Internet takes place using an Internet protocol, commonly known as IP. IP datagrams (data packets) are transmitted over links from one router to the next one on their ways towards the final destinations. In each router a forwarding decision is performed on incoming datagrams to determine the datagrams next-hop router.
A routing or forwarding decision is normally performed by a lookup procedure in a forwarding data structure such as a routing table. Thus, IP routers do a routing lookup in the routing table to obtain next-hop information about where to forward the IP datagrams on their path toward their destinations. A routing lookup operation on an incoming datagram requires the router to find the most specific path for the datagram. This means that the router has to solve the so-called longest prefix matching problem which is the problem of finding the next-hop information (or index) associated with the longest address prefix matching the incoming datagrams destination address in a set of arbitrary length (for instance between 0 and the address length) prefixes constituting the routing table.
To speed up the forwarding decisions, many IP router designs of today use a caching technique, wherein the most recently or most frequently looked up destination addresses and the corresponding routing lookup results are kept in a route cache. This method works quite well for routers near the edges of the network, i.e. so called small office and home office (SOHO) routers having small routing tables, low traffic loads, and high locality of accesses in the routing table.
Another method of speeding up the routers is to exploit the fact that the frequency of routing table updates, resulting from topology changes in the network etc., is extremely low compared to the frequency of routing lookups. This makes it feasible to store the relevant information from the routing table in a more efficient so-called “forwarding table” optimized for supporting fast lookups.
In this context, a forwarding table is an efficient representation of a routing table and a routing table is a dynamic set of address prefixes. Each prefix is associated with next hop information, i.e. information about how to forward an outgoing packet and the rules of the game state that the next-hop information associated with the longest matching prefix of the destination address (of the packet) must be used. When changes to the routing table occur, the forwarding table is partially or completely rebuilt.
An example of a forwarding data structure is a so-called “static block tree”, which is a comparison based data structure for representing w-bit non-negative integers with d-bit data and supporting extended search in time proportional to the logarithm with base B, where B−1 is the number of integers that can stored in one memory block, of the number of integers stored. Typically, it is a static data structure which supports efficient extended search with minimum storage overhead. The static block tree data structure has previously been described in the Swedish patent 0200153-5, which refers to a method and system for fast IP routing lookup using forwarding tables with guaranteed compression ratio and lookup performance where it is referred to as a Dynamic Layered Tree and also in M. Sundström and Lars-Åke Larzon, High-Performance Longest Prefix Matching supporting High-Speed Incremental Updates and Guaranteed Compression, IEEE INFOCOMM, Miami Fla., USA, 2005.
A basic block tree, for instance in the form of a dynamic layered tree, consists of at least one leaf and possibly a number of nodes if the height is larger than one. The height corresponds to the number of memory accesses required for looking up the largest stored non-negative integer smaller than or equal to a query key. This kind of lookup operation is referred to as extended search.
The problem solved by a basic block tree is to represent a partition, of a totally ordered universe U, consisting of n basic intervals. Since U is known, also minU and maxU are known. Therefore, it is sufficient to represent n−1 interval boundaries where each interval boundary is represented by an element which is a w-bit non-negative integer. The w-bit non-negative integer is referred to as the key and the corresponding d-bit data field as the data. In one memory block, we can store B elements and thus represent B+1 intervals. We call the resulting data structure a basic block tree of height 1. Each basic interval constitutes a subset of U. For each subset, we can recursively represent a partition consisting of B+1 intervals by using one additional memory block. By combining the original partition of U with the B+1 sub-partitions, we obtain a block tree of height 2 representing (B+1)2 basic intervals. Assuming that pointers to sub-structures can be encoded implicitly, it is possibly to recursively construct a block tree of arbitrary height t for representing up to (B+1)t basic intervals.
A block tree of height t that represents exactly (B+1)t intervals is said to be complete. Otherwise it is partial. The need for pointers is avoided by storing a block tree in a consecutive array of memory blocks. To store a block tree of height t, first the root block is stored in the first location. This is followed by up to B+1 recursively stored complete block trees of height t−1 and possibly one recursively stored partial block tree of height t−1. No pointers are needed since the size s(t−1) of a complete block tree of height t−1 can be computed in advance. The root of sub-tree i is located i·s(t−1) memory blocks beyond the root block (assuming that the first sub-tree has index zero).
Typically, there are two major problems with basic block trees. The first problem is related to worst case storage cost. More precisely, the worst case amortized number of bits required for storing n keys and their corresponding data may be considerably larger than n·(w+d) in the worst case resulting in a worst case cost per key of much more than w+d bits which is optimal (at least in a sense). The second problem is related to incremental updates. A basic block tree is essentially static which means that the whole data structure must be rebuilt from scratch when a new key and data is inserted or deleted. As a result, the cost for updates is too high, i.e. at least in some applications, it takes too much time and computation, in particular if the block tree is large.
Now, consider yet another general problem of designing a data structure for storing and looking up keys from a bounded universe. If we completely disregard the fact that the universe is bounded, we can simply use a comparison-based data structure such as a binary tree. We can express the efficiency of the data structure in terms of costs for storage and lookups. For a binary tree, the amount of storage used is proportional to the number of keys whereas the time for lookup is proportional to Ig n, where Ig denotes the logarithm with base 2.
As an alternative approach we could use a digital data structure such as a trie to exploit the bounded universe. An example of a trie is a fixed stride trie, which is a data structure for representing w-bit keys in t levels where level i consist of nodes represented by arrays of pointers of size 2^k[i] (2 to the power of k[i]). The numbers k[i] are called strides and a trie where each k[i] equals 1 is refereed to as a binary trie. Each pointer either refers directly to a piece of data if there is only one matching key or a node at the next (lower) level. We number the levels from t, t−1, . . . , 1 where t is the topmost level. At the topmost level, the k[t] most significant bits of the query key are used to index into the array of pointers. If the pointer retrieved refers to a sub-trie, the w−k[t] least significant bits of the query key are used recursively to complete the lookup. Fixed stride tries support extended search.
Both trees and tries are defined recursively and consists of nodes and leaves, where a query key is compared to a piece of information stored in each node and the outcome determines in which sub-structure to continue the search. Assume that the universe consists of the set of w-bit non-negative integers and compare a binary tree node with a binary trie node. The tree node contains a key which effectively partitions the universe into the left sub-universe, the right sub-universe, and the key itself. In contrast, the trie node specifies an index of a certain bit to be inspected and effectively partitions the universe into the 0-subuniverse and the 1-subuniverse consisting of all keys where the inspected bit is 0 and 1 respectively. Since the size of the universe is reduced by a factor of 2 by each trie node it follows that the maximum height as well as the worst case cost for lookup in a trie is proportional to w.
When comparing block trees with tries, for example t-level fixed stride tries, we observe a third problem with block trees namely the lookup cost. Whereas such a trie has a bounded lookup cost of t steps (or memory accesses), independently of the number of intervals, the lookup cost in a block tree grows logarithmically with the number of intervals. Another key aspect of the performance is the worst case storage costs per interval. Whereas the total storage cost in a block tree grows linearly with the number of intervals and could potentially be reduced to only w+d bits per interval using the present invention, there is an explosive growth of the worst case storage cost of a fixed stride trie if t is considerably less that w, which is typically the case since it would not make any sense otherwise to bound the lookup cost.